/*
 *Copyright (c) 2006, 2008, 2009, 2010 Edward Rosten
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 
 * 	*Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 * 
 *      *Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 * 
 * 	*Neither the name of the University of Cambridge nor the names of 
 *       its contributors may be used to endorse or promote products derived 
 *       from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package de.lmu.dbs.jfeaturelib.pointDetector.FAST;

import de.lmu.dbs.jfeaturelib.ImagePoint;
import java.util.ArrayList;
import java.util.List;

/**
 *
 * @author Robert Zelhofer
 */
public class FASTNonMaxSuppression {

    private boolean compare(double x, double y) {
        return x >= y;
    }

    public List<ImagePoint> nonmax_suppression(List<ImagePoint> corners, int[] scores, int num_corners) {
        int num_nonmax = 0;
        int last_row;
        int[] row_start;
        int i, j;
        List<ImagePoint> ret_nonmax = new ArrayList<>();

        
        int sz = num_corners;

        /*Point above points (roughly) to the pixel above the one of interest, if there
        is a feature there.*/
        int point_above = 0;
        int point_below = 0;


        if (num_corners < 1) {
            return ret_nonmax;
        }

        /* Find where each row begins
        (the corners are output in raster scan order). A beginning of -1 signifies
        that there are no corners on that row. */
        last_row = (int)corners.get(num_corners - 1).y;
        row_start = new int[last_row + 1];

        for (i = 0; i < last_row + 1; i++) {
            row_start[i] = -1;
        }

        {
            int prev_row = -1;
            for (i = 0; i < num_corners; i++) {
                if ((int)corners.get(i).y != prev_row) {
                    row_start[(int)corners.get(i).y] = i;
                    prev_row = (int)corners.get(i).y;
                }
            }
        }



        for (i = 0; i < sz; i++) {
            boolean isCorner = false;
            int score = scores[i];
            ImagePoint pos = corners.get(i);

            /*Check left */
            if (i > 0) {
                if (corners.get(i - 1).x == pos.x - 1 && corners.get(i - 1).y == pos.y && compare(scores[i - 1], score)) {
                    continue;
                }
            }

            /*Check right*/
            if (i < (sz - 1)) {
                if (corners.get(i + 1).x == pos.x + 1 && corners.get(i + 1).y == pos.y && compare(scores[i + 1], score)) {
                    continue;
                }
            }

            /*Check above (if there is a valid row above)*/
            if (pos.y != 0 && row_start[(int)pos.y - 1] != -1) {
                /*Make sure that current point_above is one
                row above.*/
                if (corners.get(point_above).y < pos.y - 1) {
                    point_above = row_start[(int)pos.y - 1];
                }

                /*Make point_above point to the first of the pixels above the current point,
                if it exists.*/
                for (; corners.get(point_above).y < pos.y && corners.get(point_above).x < pos.x - 1; point_above++) {
                }


                for (j = point_above; corners.get(j).y < pos.y && corners.get(j).x <= pos.x + 1; j++) {
                    double x = corners.get(j).x;
                    if ((x == pos.x - 1 || x == pos.x || x == pos.x + 1) && compare(scores[j], score)) {
                        isCorner = false;
                        continue;
                    } else {
                        isCorner = true;
                    }
                    
                    
                }

            }

            /*Check below (if there is anything below)*/
            if (pos.y != last_row && row_start[(int)pos.y + 1] != -1 && point_below < sz) /*Nothing below*/ {
                if (corners.get(point_below).y < pos.y + 1) {
                    point_below = row_start[(int)pos.y + 1];
                }

                /* Make point below point to one of the pixels belowthe current point, if it
                exists.*/
                for (; point_below < sz && corners.get(point_below).y == pos.y + 1 && corners.get(point_below).x < pos.x - 1; point_below++) {
                }

                for (j = point_below; j < sz && corners.get(j).y == pos.y + 1 && corners.get(j).x <= pos.x + 1; j++) {
                    double x = corners.get(j).x;
                    if ((x == pos.x - 1 || x == pos.x || x == pos.x + 1) && compare(scores[j], score)) {
                        isCorner = false;
                        continue;
                    } else {
                        isCorner = true;
                    }
                    
                    
                }
            }
            
            ret_nonmax.add(corners.get(i));
            
        }
        return ret_nonmax;
    }
}
